package tree.递归;

import po.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N出现次数最多的子树元素和508.java
 * @Description https://leetcode-cn.com/problems/most-frequent-subtree-sum/
 * @createTime 2021年05月14日 20:18:00
 */
public class N出现次数最多的子树元素和508 {

    /**
     *  用hashmap保存和出现的次数
     */
    Map<Integer,Integer> hashMap=new HashMap<>();
    Integer max=0;
    public int[] findFrequentTreeSum(TreeNode root) {

        if (root == null) {
            return null;
        }
        //用后续遍历的方式求节点的和
        count(root);

        //用数组装出现次数最多的
        ArrayList<Integer> list = new ArrayList<>();
        for(int i : hashMap.keySet()){
            if(hashMap.get(i).equals(max)){
                list.add(i);
            }
        }
        int[] result = new int[list.size()];
        for(int i = 0; i<result.length; i++){
            result[i] = list.get(i);
        }
        return result;
    }

    private Integer count(TreeNode node) {
        if (node == null) {
            return 0;
        }
        //使用后续遍历的方式
        Integer leftCount = count(node.left);
        Integer rightCount = count(node.right);
        //保存节点的元素和
        int count = node.val + leftCount + rightCount;
        hashMap.put(count,hashMap.getOrDefault(count,0)+1);
        //记录出现次数最大值
        max = Math.max(max, hashMap.get(count));
        return count;
    }
}
